package org.raymond.iworks.study.basic.algorithm.sort;

import java.util.Arrays;

/**
 * 基数排序:桶排序的扩展
 * 初始化10个桶:从0到9,每个桶都是一个一维数组
 *
 * arr = {53,3,542,748,14,214}
 * 第一轮排序:
 * 1)将每个元素的个位数取出,然后看这个数应该放在哪个对应的桶内
 * 桶2:542
 * 桶3:53,3
 * 桶4:14,214
 * 桶8:748
 * 2)按照这个桶的顺序(一维数组的下标)依次取出数据,放入原数组
 * arr={542,53,3,14,214,748}
 *
 * 第二轮排序:
 * 1)将每个元素的十位数取出,然后看这个数应该放在哪个对应的桶内
 * 桶0:03
 * 桶1:14,214
 * 桶4:542,748
 * 桶5:53
 * 2)按照这个桶的顺序(一维数组的下标)依次取出数据,放入原数组
 * arr={3,14,214,542,748,53}
 *
 * 第三轮排序:
 * 1)将每个元素的百位数取出,然后看这个数应该放在哪个对应的桶内
 * 桶0:003,014,053
 * 桶2:214
 * 桶5:542
 * 桶7:748
 *
 * 2)按照这个桶的顺序(一维数组的下标)依次取出数据,放入原数组
 * arr={3,14,53,214,542,748}
 *
 * 轮数==最大数的位数,排序结束
 *
 * 说明:
 * 1) 基数排序是对传统桶排序的扩展,速度很快
 * 2) 基数排序是经典的空间换时间的方式,占用内存很大,当对海量数据排序时,容易造成OOM
 * 3) 基数排序是稳定的.[注:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,
 * 这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前，而在排序后的序列中,
 * r[i]仍在r[j]之前,则称这种排序算法是稳定的,否则称为不稳定的]
 * 4) 有负数的数组,我们不用基数排序来进行排序,如果要支持负数,参考:
 * https://code.i-harness.com/zh-CN/q/e98fa9
 */
public class RadixSortTest {
    public static void main(String[] args) {
        int[] arr = newArr();
        // arr = new int[]{53,3,542,748,14,214};
        //System.out.printf("待排序数组:%s\n", Arrays.toString(arr));
        int[] cloned = Arrays.copyOf(arr, arr.length);
        long start = System.nanoTime();
        radixSort(arr);
        long end = System.nanoTime();
        // System.out.printf("基数排序结果:%s\n", Arrays.toString(arr));
        // post: 21,436,843 纳秒, 约21毫秒, 100,000个元素的数组
        System.out.printf("耗时:%d\n", (end-start));

        start = System.nanoTime();
        SelectSortTest.jdkSort(cloned);
        end = System.nanoTime();
        // System.out.printf("排序结果:%s\n", Arrays.toString(arr));
        // post: 19,375,459 纳秒, 约19毫秒, 100,000个元素的数组
        System.out.printf("jdksort 耗时:%d\n", (end-start));
    }

    public static void radixSort0(int[] arr){
        // 定义一个二维数组,表示桶标识为0~9的共10个桶,每个桶都是一个一维数组,
        // 每个桶的标识对应待排序的数各个位上的数
        // 说明:
        // 1,二维数组包含10个一维数组
        // 2,为了防止在放入数的时候,数据溢出,则每个一维数组(桶),大小定为arr.length.这样可以容纳极端情况下
        // 不同位数上的数都是同一个数的情况
        // 3,基数排序是使用空间换时间的经典算法
        int[][] bucket = new int[10][arr.length];

        // 为了记录每个桶中,实际存放了多少个数据,我们定义一个一维数组,来记录各个桶
        // 每次放入的数据的个数
        // bucketElementCounts[0],记录的就是 bucket[0] 桶中放入数据的个数
        int[] bucketElementCounts = new int[10];

        // 第1轮(针对每个元素的个位进行排序
        for(int j=0; j<arr.length; j++){
            // 取出每个元素的个位的值
            int digitOfElement = arr[j]/1 % 10;
            System.out.printf("arr[j]=%s, digitOfElement=%s\n", arr[j], digitOfElement);
            // 放入到对应的桶中:
            // bucketElementCounts[digitOfElement] 表示标识为digitOfElement的桶中放入了多少个数据
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            // 当前已放入一个数据,即++
            bucketElementCounts[digitOfElement]++;
        }
        // 按照这个桶的顺序(一维数组的下标,bucket[k])依次取出数据,放入原来数组
        int index = 0;
        // 遍历每个桶,并将桶中的数据,放入到原数组
        for(int k=0; k<bucketElementCounts.length; k++){
            // 如果桶中,有数据,我们才放入到原数组
            if(bucketElementCounts[k]!=0){
                // 循环该桶,即第k个桶(即第k个一维数组),放入
                for(int l=0;l<bucketElementCounts[k];l++){
                    //取出元素放入arr
                    arr[index++]=bucket[k][l];
                }
            }
            // 第1轮处理后,需要将每个bucketElementCounts[k]=0
            bucketElementCounts[k]=0;
        }

        System.out.println("第1轮,对个位的排序处理 arr="+ Arrays.toString(arr));

        // ====================================================================

        // 第2轮(针对每个元素的个位进行排序
        for(int j=0; j<arr.length; j++){
            // 取出每个元素的十位的值
            int digitOfElement = arr[j]/10 % 10;
            // 放入到对应的桶中:
            // bucketElementCounts[digitOfElement] 表示标识为digitOfElement的桶中放入了多少个数据
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            // 当前已放入一个数据,即++
            bucketElementCounts[digitOfElement]++;
        }
        // 按照这个桶的顺序(一维数组的下标,bucket[k])依次取出数据,放入原来数组
        index = 0;
        // 遍历每个桶,并将桶中的数据,放入到原数组
        for(int k=0; k<bucketElementCounts.length; k++){
            // 如果桶中,有数据,我们才放入到原数组
            if(bucketElementCounts[k]!=0){
                // 循环该桶,即第k个桶(即第k个一维数组),放入
                for(int l=0;l<bucketElementCounts[k];l++){
                    //取出元素放入arr
                    arr[index++]=bucket[k][l];
                }
            }
            // 第2轮处理后,需要将每个bucketElementCounts[k]=0
            bucketElementCounts[k]=0;
        }

        System.out.println("第2轮,对个位的排序处理 arr="+ Arrays.toString(arr));


        // =========================================
        // 第3轮(针对每个元素的个位进行排序
        for(int j=0; j<arr.length; j++){
            // 取出每个元素的十位的值
            int digitOfElement = arr[j]/100 % 10;
            // 放入到对应的桶中:
            // bucketElementCounts[digitOfElement] 表示标识为digitOfElement的桶中放入了多少个数据
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            // 当前已放入一个数据,即++
            bucketElementCounts[digitOfElement]++;
        }
        // 按照这个桶的顺序(一维数组的下标,bucket[k])依次取出数据,放入原来数组
        index = 0;
        // 遍历每个桶,并将桶中的数据,放入到原数组
        for(int k=0; k<bucketElementCounts.length; k++){
            // 如果桶中,有数据,我们才放入到原数组
            if(bucketElementCounts[k]!=0){
                // 循环该桶,即第k个桶(即第k个一维数组),放入
                for(int l=0;l<bucketElementCounts[k];l++){
                    //取出元素放入arr
                    arr[index++]=bucket[k][l];
                }
            }
            // 第3轮处理后,需要将每个bucketElementCounts[k]=0
            bucketElementCounts[k]=0;
        }

        System.out.println("第3轮,对个位的排序处理 arr="+ Arrays.toString(arr));
    }

    public static void radixSort(int[] arr){
        // 根据radixSort0的推导过程,我们可以得到最终的基数排序代码
        // 1,得到数组中最大的位数
        int max = arr[0]; //假设第一数就是最大数
        for(int i=1; i<arr.length; i++){
            if(arr[i]>max){
                max=arr[i];
            }
        }
        // 得到最大数是几位数
        int maxBitLength = (max+"").length();

        // 定义一个二维数组,表示标识为0~9的共10个桶,每个桶都是一个一维数组,
        // 每个桶的标识对应待排序的数各个位上的数
        int[][] bucket = new int[10][arr.length];
        // 记录每个桶在每一轮排序中放入轮多少个数据
        int[] bucketElementCounts = new int[10];

        for(int i=0, n=1; i<maxBitLength; i++, n*=10) {
            // 针对每个元素的对应位进行排序处理,第一轮是个位,第二轮是十位,第三轮是百位
            for (int j=0; j<arr.length; j++) {
                // 取出每个元素在当前轮次中需要排序的位的值
                int digitOfElement = arr[j] / n % 10;
                // 放入到对应的桶中:
                // bucketElementCounts[digitOfElement] 表示标识为digitOfElement的桶中放入了多少个数据
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                // 当前已放入一个数据,需要++做记录
                bucketElementCounts[digitOfElement]++;
            }
            // 按照这个桶的顺序(一维数组的下标,bucket[k])依次取出数据,放入原来数组
            int index = 0;
            // 遍历每个桶,并将桶中的数据,放入到原数组
            for (int k = 0; k < bucketElementCounts.length; k++) {
                // 如果桶中,有数据,我们才放入到原数组
                if (bucketElementCounts[k] != 0) {
                    // 循环该桶,即第k个桶(即第k个一维数组),放入
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        //取出元素放入arr
                        arr[index++] = bucket[k][l];
                    }
                }
                // 第1轮处理后,需要将每个bucketElementCounts[k]=0
                bucketElementCounts[k] = 0;
            }
        }
    }

    public static int[] newArr(){
        int[] arr = new int[10_000_000];
        for(int i=0; i<arr.length; i++){
            arr[i]=(int)(Math.random()* 10_000_000);
        }
        return arr;
    }
}
